# 回溯，单词搜索


class Solution:

    def exist(self, board, word):

        def dfs(i, j, k):
            """
            k 表示 word的第0个字母
            """
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
                return False
            # 找到最后一层
            if k == len(word) - 1:
                return True
            # 用过的标记为空，避免重复使用
            board[i][j] = ''
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k+1) or dfs(i, j+1, k+1) or dfs(i, j-1, k+1)
            board[i][j] = word[k]
            return res



        for i in range(len(board)):

            for j in range(len(board[0])):
                
                if dfs(i, j, 0):
                    return True
                
        
        return False




if __name__ == "__main__":

    board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]

    word = "ABCCED"
    sol = Solution()
    res = sol.exist(board, word)
    print(res)


